\section{辗转相除与 Bézout 等式}

\begin{frame}{最大公因子}
  \begin{definition}%定义1
    [最大公因子] 设 $a, b$ 为整数， 若有整数 $d$ 满足： 
    (1)  $d$ 是 $a$ 和 $b$的公因子;
    (2) $a$ 和 $b$ 的任意公因子都是 $d$ 的因子， 
    则称 $d$ 是 $a$ 和 $b$ 的一个\emph{最大公因子} (greatest common divisor, 简写为 gcd).
\end{definition}
\pause
例如，若$a\mid b$, 则$a$为$a,b$的最大公因子。
\pause
最大公因子一般的存在性将在下面证明。 
\pause
现在看它的唯一性 (除非相差正负号):
\pause
若 $d$ 和 $d^{\prime}$ 都是 $a$ 和 $b$ 的最大公因子， 则应 $d^{\prime} \mid d$ 且 $d \mid d^{\prime}$, 从而 $d=d^{\prime} q, d^{\prime}=d r=$ $d^{\prime} q r, 1=q r, q= \pm 1$, 故 $d^{\prime}= \pm d$. 
\pause
故 $a$ 和 $b$ 的正的最大公因子 $d$ 是唯一的， 以 $(a, b)$ 或 $\operatorname{gcd}(a, b)$ 记之。 
\footnote{注意$0,0$的惟一最大公因子为$0$. 这个平凡的情况我们通常忽略即可。
$(a,b)$这个记号默认$a,b$不全为零。}
\pause
例如 $(4,6)=2,(-4,6)=2,(4,0)=4$.
%易知 $(a, b)=(a-b, b)=(a-2 b, b)=(a-q b, b)$, 故有：

\pause
\begin{theorem}%定理1
若 $a=b q+r$, 其中 $a, b, r$ 为整数 ($a, b$ 不全为 $0$), 则
$a,b$的公因子与$r,b$的公因子相同 (构成的集合相等)。特别地，若$(r,b)$存在，则
  $(a, b)=(r, b).$
\end{theorem}

\pause
\begin{proof}
  若$c$为$a,b$的公因子，则$a\mid r=a-bq$, 故$c$为$r,b$的公因子。
  反过来，若$c$为$r,b$的公因子，则$c\mid a=bq+r$, 故$c$为$a,b$的公因子。
 \end{proof}
 \end{frame}

 \begin{frame}{辗转相除与 Bézout 等式}
   定理 1 说明，余数 $r$ 可做原数 $a$ 的 “替身”去求最大公因子。 我们又可找 $b$的替身 $r_{1}$ 代替 $b$, 等等。 
\pause
   如此继续， 就是著名的\emph{辗转相除法} (Euclidean algorithm) :
\[
  \begin{aligned}
  a&= b q_{0}+r_{1}, \quad 0<r_{1}<|b|, \\
  \pause
b&= r_{1} q_{1}+r_{2}, \quad 0<r_{2}<r_{1}, \\
\pause
r_{1}&= r_{2} q_{2}+r_{3}, \quad 0<r_{3}<r_{2}, \\
\pause
& \cdots \cdots \cdots \cdots \cdots \\
\pause
r_{s-2}&= r_{s-1} q_{s-1}+r_{s}, \quad 0<r_{s}<r_{s-1}, \\
\pause
r_{s-1}&= r_{s} q_{s} \quad\left(r_{s+1}=0\right) .
\end{aligned}
\]
\pause
其中不完全商 $q_{i}$ 和余数 $r_{i}$ 都是逐步唯一确定的。
\pause
为了记号统一，可记 $b=r_{0}, a=r_{-1}$;
这样$b\mid a$的情形（这时不必辗转）相当于$s=0$.
\pause
因为非负余数 $r_{1}, r_{2}, \cdots$ 逐步减小， 终会为零， 故可设 $r_{s+1}=0$, 即 $r_{s} \mid r_{s-1}$. 
\pause
从后往前看知
\[
  r_{s} = \left(r_{s-1}, r_{s}\right)
  \pause
=\left(r_{s-2}, r_{s-1}\right)
\pause
  =\cdots=\left(r_{1}, r_{2}\right)=\left(r_{1}, b\right)=(a, b).
\]

\vspace*{-1em}
\pause
\begin{theorem}%定理2
  不全为零的两整数 $a, b$ 的正最大公因子 $d=(a, b)$ 是唯一存在的， 即 $d=r_{s}$.
%($a\nmid b$或$b\nmid a$时就是 $a$ 与 $b$ 辗转相除的最后非零余数). 
而且存在整数 $u, v$ 使
\[\tag{$*$}
  u a+v b=d.
\]
\end{theorem}
\pause
($*$) 式称为 \emph{Bézout (贝祖) 等式} (Bézout's identity)。

\end{frame}

\begin{frame}

 \begin{proof}
  只需证 Bézout 等式%。
%  我们对$i$ ($i=0, \cdots, s$)  归纳来证明$r_i$可写为$a,b$的整系数的线性组合。
%  $i=0$时$r_0=b$, 情形平凡。
%  令$0<i\leqslant s$. 假设结论对所有$r_1,\cdots,r_{s-1}$成立。
%  因此$r_{s-2}=u_1 a+v_1b, r_{s-1}=u_2a+v_2b$.
%  进而
%  \[
%    r_s=r_{s-2}- r_{s-1} q_{s-1}=(u_1-u_2q_{s-1})a+(v_1-v_2q_{s-1})b,
%  \]
%  如我们期望的。
：从前向后看辗转相除诸式。 
首先有
\[
r_{s}=r_{s-2}-r_{s-1} q_{s-1}
\]
而再前一式为 $r_{s-1}=r_{s-3}-r_{s-2} q_{s-2}$, 以此 $r_{s-1}$ 代人上式， 可知 $r_{s}$ 是 “ $r_{s-2}$ 和 $r_{s-3}$ 的整数倍之和”. 再前推一式以 $r_{s-2}$ 代人， 可得 $r_{s}$ 是 “ $r_{s-3}$ 和 $r_{s-4}$ 的整数倍之和”. 由此不断上推， 最终可得 $r_{s}$ 是 “ $a$ 与 $b$ 的整数倍之和”, 即得 Bézout 等式。
\end{proof}

\pause
当$(a, b)=1$ 时， 称 $a$ 与 $b$ \emph{互素} (relatively prime, coprime).

\pause
\begin{corollary}%系1
两整数 $a, b$ 互素当且仅当存在整数 $u, v$ 使
\[
u a+v b=1 \quad\text { (Bézout 等式). }
\]
\end{corollary}

\pause
\begin{proof}
 若 $u a+v b=1$, 因 $(a, b)$ 整除 $a$ 与 $b$, 故整除右边的 $1$, 从而 $(a, b)=1$.
 反之， 若 $(a, b)=1$, 则由定理 2 知 $u a+v b=1$ 成立。
 \end{proof}

 \pause
 定理2和系 1 中的 $u, v$ 称为 \emph{Bézout 系数}， 不是唯一的。 可以递归求出。将在习题 1.4 的 6,7 等习题和连分数等处进一步讨论。
\end{frame}

\begin{frame}
    \begin{example}%例1
    [秦九韶：大衍求一术]
    求解方程 $65 x+83 y=1$.
\end{example}
\pause
\begin{solution}
  作辗转相除反复推演 (大衍) 得
\[
83=65 \cdot 1+18,65=18 \cdot 3+11,18=11+7,11=7+4,11=4 \cdot 2+3,4=3+1
\]
最后得非零余数 $d=1$ (大衍求索最终得到一). 再从后往前推演诸式， 得
\[
  \begin{aligned}
    1 & =4-3=4-(11-4 \cdot 2)=3 \cdot 4-11=3 \cdot(11-7)-11=2 \cdot 11-3 \cdot 7 \\
  & =2 \cdot 11-3 \cdot(18-11)=5 \cdot 11-3 \cdot 18=5 \cdot(65-3 \cdot 18)-3 \cdot 18 \\
& =5 \cdot 65-18 \cdot 18=5 \cdot 65-18 \cdot(83-65)=23 \cdot 65-18 \cdot 83
\end{aligned}
\]
即得到 Bézout 等式 $1=23 \cdot 65-18 \cdot 83$. 故得原方程的一个解 $x=23, y=-18$.
\pause
(在$\ZZ$上的通解为$(x,y)=(23-83k, -18+65k)$, 其中$k\in \ZZ$.)
\end{solution}

\pause
 \begin{corollary}%系2
   设 $a, b$ 为整数， $(a, b)=d$, 则
 \[
 \{a m+b n \mid m, n \in \mathbb{Z}\}=\{d k \mid k \in \mathbb{Z}\}
 \]
 \end{corollary}


\end{frame}

\begin{frame}



 \begin{explain*}%说明
 常将 $\{a m+b n \mid m, n \in \mathbb{Z}\}$ 简记为 $a \mathbb{Z}+b \mathbb{Z}$ 或 $(a, b)$. 故上式也可记为
 \[
 a \mathbb{Z}+b \mathbb{Z}=d \mathbb{Z}, \quad \text { 或 } \quad(a, b)=(d).
 \]
 实际上，$d$正是$\ZZ$的理想$(a,b)$的生成元（回想下$\ZZ$是主理想整环）。
 \end{explain*}
\pause
 \begin{proof}
  $a m+b n$ 显然是 $d$ 的倍数。 另一方面， 由 Bézout 等式知$d$可写为 $d=u a+v b$, 故
\[
k d=k u a+k v b=m a+n b .
\]
\end{proof}
\pause
 系 2 表明， 由 $x a+y b=c$ 只能得出 $(a, b) \mid c$. 另外注意， Bézout 等式的系数 $u, v$ 不是唯一的，例如 $d=u a+v b=(u-2 b) a+(v+2 a) b$.

 ~

\pause
任意 $s$ 个整数 $a_{1}, \cdots, a_{s}$ 的\emph{最大公因子} $d$ 可类似 $s=2$ 情形定义， 即定义 $d$ 满足\\
 (1) $d \mid a_{i}$ ($i=1, \cdots, s$);\\
  (2) 若 $\delta \mid a_{i}$ ($i=1, \cdots, s$), 则 $\delta \mid d$.\\
  \pause
  显然 $a_{1}, \cdots, a_{s}$ 的两个最大公因子可互相整除，故最多相差正负号，
  其中正的最大公因子(若这些$a_i$不全为零)记为 $\left(a_{1}, \cdots, a_{s}\right)$ 
  或 $\operatorname{gcd}\left(a_{1}, \cdots, a_{s}\right)$. 
  若 $\left(a_{1}, \cdots, a_{s}\right)=1$, 则称 $a_{1}, \cdots, a_{s}$ \emph{互素}（读者注意这与“ $a_{1}, \cdots, a_{s}$ 两两互素”的区别）.

\end{frame}

 \begin{frame}

\begin{theorem}%定理3
  任意 $s\geqslant 2$ 个不全为零的整数 $a_{1}, \cdots, a_{s}$ 的正最大公因子 
  $d=\left(a_{1}, \cdots, a_{s}\right)$ 存在且唯一， 且若$a_{1}, \cdots, a_{s-1}$
  不全为零，则
\[
  \left(a_{1}, \cdots, a_{s-1}, a_{s}\right)=\left(\left(a_{1}, \cdots, a_{s-1}\right), a_{s}\right).
\]
而且，存在整数 $u_{1}, \cdots, u_{s}$ 使得
\[
u_{1} a_{1}+\cdots+u_{s} a_{s}=d \quad \text { (Bézout 等式). }
\]
\end{theorem}
\pause
 \begin{proof}
%由最大公因子定义可知， $\left(a_{1}, \cdots, a_{s}\right)$ 整除 $a_{i}$ ($i=1, \cdots, s$), 
%从而整除 $\left(a_{1}, \cdots, a_{s-1}\right)$ 与 $a_{s}$, 
%从而整除 $\left(\left(a_{1}, \cdots, a_{s-1}\right), a_{s}\right)$. 
%同理可知 $\left(\left(a_{1}, \cdots, a_{s-1}\right), a_{s}\right)$ 整除 $\left(a_{1}, \cdots, a_{s}\right)$. 因二者均为正整数， 故相等。 由此等式可归纳地得出，$3$ 个，$4$ 个，$\cdots$, 任意 $s$ 个整数 $a_{1}, \cdots, a_{s}$ 的最大公因子 $d$是存在的。 假设 $s-1$ 个整数情形的 Bézout 等式成立， 设为
%\[
%u_{1} a_{1}+\cdots+u_{s-1} a_{s-1}=\left(a_{1}, \cdots, a_{s-1}\right)
%\]
%则应存在整数 $u, v$ 使得
%\[
%\begin{aligned}
%d & =\left(a_{1}, \cdots, a_{s-1}, a_{s}\right)=\left(\left(a_{1}, \cdots, a_{s-1}\right), a_{s}\right)=u\left(a_{1}, \cdots, a_{s-1}\right)+v a_{s} \\
%& =u\left(u_{1} a_{1}+\cdots+u_{s-1} a_{s-1}\right)+v a_{s}=u u_{1} a_{1}+\cdots+u u_{s-1} a_{s-1}+v a_{s}
%\end{aligned}
%\]
%这就得到 $s$ 个整数情形的 Bézout 等式。
%
    我们对$s\geqslant 2$归纳来证明最大公因子存在。$s=2$的情形已知，假设$s>2$. 不妨设$a_1\neq 0$. 
    由归纳假设，$d'=(a_1, \cdots, a_{s-1})$存在。 
    令$d=(d', a_s)$. 显然$d\mid a_i$, 对所有$i$. 另一方面，若$\delta$为$a_1,a_2,\cdots,a_s$的公因子，
    则$\delta\mid d', \delta\mid a_s$, 从而$\delta\mid d$. 
    因此$d$为$a_1, a_2, \cdots, a_s$的最大公因子。唯一性由整除的互伴性易知。

    我们同样对$s$归纳来证明B\'ezout等式存在。只用对$d$证明且只用考虑$s>2$. 由归纳假设，存在$c_1, \cdots, c_{s-1}, u, v\in \ZZ$使得
  \[
      c_1a_1+\cdots+c_{s-1}a_{s-1}=d',\qquad ud'+va_s=d.
  \]
  这样\[
      (uc_1)a_1+\cdots+(uc_{s-1})a_{s-1}+va_s=d.
  \]

\end{proof}
\end{frame}

\begin{frame}
\begin{example}%例2
设 $\delta$ 是 $a$ 和 $b$ 的正公因子， $k$ 为正整数， $a, b$ 是不全零的整数。
那么
\[
  (a k, b k)=(a, b) k ;\quad (a / \delta, b / \delta)=(a, b) / \delta.
\]
特别可知， 当 $d=(a, b)$ 时， $(a / d, b / d)=1$.
\end{example}

\pause
\begin{solution*}%解
  将所有的整数都放大 $k$ 倍， 则它们之间的整除关系是保持的， 故若 $a, b$ 的最大公因子是 $d$, 则 $a k, b k$ 的最大公因子为 $d k$. 另外证法是： 由 Bézout 等式
\[
u a+v b=(a, b)
\]
得
\[
u a k+v b k=(a, b) k
\]
因 $(a k, b k) \mid u a k+v b k$, 故 $(a k, b k) \mid(a, b) k$. 因 $(a, b) k \mid a k$ 与 $b k$, 故 $(a, b) k \mid(a k, b k)$, 从而二者相等。 再由上述可知
\[
(a / \delta, b / \delta) \delta=(a, b)
\]
即得
\[
(a / \delta, b / \delta)=(a, b) / \delta
\]
\end{solution*}
\end{frame}

\begin{frame}

\begin{example}%例3
证明： (1) 若 $a \mid b c,(a, b)=1$, 则 $a \mid c$.

(2) 若 $a\mid c, b\mid  c,(a, b)=1$, 则 $a b \mid c$.
\end{example}
\pause
\begin{proof}
 (1) $u a+v b=1, u a c+v b c=c, a \mid$ 左边， 故 $a \mid c$.

  (2) 设 $c=b q$. 由 $a \mid c$ 即 $a \mid b q$, 以及 $(a, b)=1$, 
  由 (1) 知 $a \mid q$, 故 $c=b q= b a q_{1}, a b \mid c$.
\end{proof}
\pause
\begin{comment*}%评述
  辗转相除法最早出现于 Euclid 的《几何原本》, 故也称为 Euclid 算法(Euclidean algorithm), 是可以追溯到 3000 年前的古老算法， 是求最大公因子的奇妙方法 (不需要预先分解因子). 其方法和所得 Bézout 等式， 意义深远。近现代用到现代数论， 多项式、欧环、纽结， 到天文， 历法， 乐律， 密码和各种算法等不可胜数的理论发展和实际应用中。 中国也独立发现(见于《九章算术》等), 秦九韶谓之“大衍求一术”. 论数者单赞这“辗转相除之妙”曰：
  \begin{poem}
  千古神算数辗转， 天地轮回翻大衍。\\
到底大道归于一， 能推律历规矩天。
\end{poem}
\end{comment*}
\end{frame}

\begin{frame}
  \begin{enumerate}
    \item 考虑整数。何为最大公因子？
    \item 解释下如何辗转相除得到两个不全为零的整数的最大公因子。
      解释下此法的可行性。
    \item 何为B\'ezout等式？
    \item 何为互素？有哪些等价的条件？
    \item 多个整数的最大公因子如何定义？存在性、唯一性如何？B\'ezout等式？
    \item 如何递归地计算多个整数的正最大公因子？举例说明。
    \item 说说你知道的关于最大公因子、整除、互素的更多的事实。多多益善。
  \end{enumerate}
\end{frame}
